﻿#pragma once

//key/value模型
enum Color
{
	BLACK,
	RED,
};
template<class T>
struct RBTreeNode
{
	RBTreeNode(const T& data=T(),Color color = RED )
		:_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(color)
	{
	}
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	Color _col;
	T _data;
};
template<class T,class Ref,class Ptr>
struct __TreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __TreeIterator<T,Ref,Ptr> Self;
	__TreeIterator(Node* node):_node(node)
	{
	}
	Node* _node;
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
	Self& operator++()
	{
		if (_node->_right)
		{
			Node* subl = _node->_right;
			while (subl->_left)
			{
				subl = subl->_left;
			}
			_node = subl;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
	Self& operator--()
	{
	
		if (_node->_left)
		{
			Node* subr = _node->_left;
			while (subr->_right)
			{
				subr = subr->_right;
			}
			_node = subr;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
	bool operator==(const Self& s)
	{
		return _node == s._node;
	}
};

template<class K, class T,class KOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
	
public:
	typedef __TreeIterator<T, T&, T*> iterator;
	typedef __TreeIterator<T,const T&,const T*> const_iterator;
	iterator begin()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return iterator(cur);
	}
	iterator end()
	{
		return iterator(nullptr);
	}
	pair<iterator,bool> Insert(const T& data)
	{
		//1.按搜索树规则插入
		/*为空，直接新增插入*/
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(iterator(_root),true);
		}
		KOfT koft;
		/*不为空，找到插入位置*/
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (koft(cur->_data) >koft(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (koft(cur->_data) < koft(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
				return make_pair(iterator(cur), false);;
		}
		cur = new Node(data);
		Node* newnode = cur;
		if (koft(parent->_data) > koft(data))
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		//2.插入红节点
		cur->_col = RED;//默认非跟节点的插入默认为红色
		// 2.1 如果父节点为黑，则结束
		// 2.2 否则父节点为红-》推断》 祖父节点一定存在，且为黑
		// 重点观察叔节点
			// 叔叔存在-且为红：父、叔叔节点变为黑色；祖父变为红，继续向上处理，祖父作为当前节点、父节点向上找
			// 叔叔不存在 或 叔叔存在且为黑 ： 先旋转，再变色 
		while (parent&&parent->_col == RED)
		{
			//找再上层父节点
			Node* grandfather = parent->_parent;
			if (grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;
				//叔叔存在
				if (uncle&&uncle->_col==RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				//叔叔不存在或为黑
				else
				{
					if (cur == parent->_right)
					{
						RotateL(parent);
						swap(parent,cur);
					}
					RotateR(grandfather);
					grandfather->_col = RED;
					parent->_col = BLACK;
					break;
				}
			}
			else
			{
				Node* uncle = grandfather->_left;
				//叔叔存在
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				//叔叔不存在
				else
				{
					if (cur == parent->_left)
					{
						RotateR(parent);
						swap(parent,cur);
					}
					RotateL(grandfather);
					grandfather->_col = RED;
					parent->_col = BLACK;
					break;
				}
			}
		}
		_root->_col = BLACK;
		
		return make_pair(iterator(newnode), true);
	}
	void RotateL(Node* prt)
	{
		//左单旋
		// 涉及的三个位置分别为不平衡根节点prt<subrl<subr：1.subr的subrl给prt右// 2.prt变为subr左
		// 更新每个节点的parent：subrl的parent// prt的parent// subr的parent 
		Node* subr = prt->_right;
		Node* subrl = subr->_left;
		prt->_right = subrl;
		subr->_left = prt;

		if (subrl)subrl->_parent = prt;
		Node* prt_p = prt->_parent;
		prt->_parent = subr;
		if (_root == prt)
		{
			_root = subr;
			subr->_parent = nullptr;
		}
		else
		{
			if (prt_p->_left == prt)prt_p->_left = subr;
			else prt_p->_right = subr;
			subr->_parent = prt_p;
		}
	}
	void RotateR(Node* prt)
	{
		//右单旋
		// 涉及的三个位置分别为不平衡根节点prt>sublr>subl： 1.subl的sublr给prt左// 2.prt变为subl右
		// 更新每个节点的parent：sublr的parent// prt的parent// subl的parent
		Node* subl = prt->_left;
		Node* sublr = subl->_right;
		prt->_left = sublr;
		subl->_right = prt;

		if (sublr)sublr->_parent = prt;
		Node* prt_p = prt->_parent;
		prt->_parent = subl;
		if (_root == prt)
		{
			_root = subl;
			subl->_parent = nullptr;
		}
		else
		{
			if (prt_p->_left == prt)prt_p->_left = subl;
			else prt_p->_right = subl;
			subl->_parent = prt_p;
		}
	}

	void _Inorder(Node* root)
	{
		KOfT koft;
		if (root == nullptr)return;
		_Inorder(root->_left);
		cout << koft(root->_data) << ":" << "root->_kv.second" << endl;
		_Inorder(root->_right);
	}
	void Inorder()
	{
		_Inorder(_root);
	}
	bool IsValidRBTree()
	{
		Node* pRoot = _root;
		// 空树也是红黑树
		if (nullptr == pRoot)
			return true;
		// 检测根节点是否满足情况
		if (BLACK != pRoot->_col)
		{
			cout << "违反红黑树性质二：根节点必须为黑色" << endl;
			return false;
		}
		// 获取任意一条路径中黑色节点的个数
		size_t blackCount = 0;
		Node* pCur = pRoot;
		while (pCur)
		{
			if (BLACK == pCur->_col)
				blackCount++;
			pCur = pCur->_left;
		}
		// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
		size_t k = 0;
		return _IsValidRBTree(pRoot, k, blackCount);
	}
	bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
	{
		//走到null之后，判断k和black是否相等
		if (nullptr == pRoot)
		{
			if (k != blackCount)
			{
				cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
				return false;
			}
			return true;
		}
		// 统计黑色节点的个数
		if (BLACK == pRoot->_col)
			k++;
		// 检测当前节点与其双亲是否都为红色
		Node* pParent = pRoot->_parent;
		if (pParent && RED == pParent->_col && RED == pRoot->_col)
		{
			cout << "违反性质三：没有连在一起的红色节点" << endl;
			return false;
		}
		return _IsValidRBTree(pRoot->_left, k, blackCount) &&
			_IsValidRBTree(pRoot->_right, k, blackCount);
	}
	iterator Find(const K& key)
	{
		KOfT koft;
		Node* cur = _root;
		while (cur)
		{
			if (koft(cur->_data) > koft(key))
			{	
				cur = cur->_left;
			}
			else if (koft(cur->_data) < koft(key))
			{
				cur = cur->_right;
			}
			else
				return iterator(cur);
		}
		return iterator(nullptr);
	}
private:
	Node* _root = nullptr;

};

//void TestRBTree1()
//{
//	cout << "TestRBTree1" << endl;
//	RBTree<int, int> RBt;
//	int arr[] = { 16,3,7,11,9,26,18,14,15 };
//	for (auto a : arr)
//	{
//		RBt.Insert(pair<int, int>(a, a));
//	}
//	RBt.Inorder();
//	cout << RBt.IsValidRBTree() << endl;
//
//	cout << "TestRBTree1" << endl;
//}